package 回溯算法.子集_组合_排列;

import java.util.LinkedList;
import java.util.List;

public class 组合_77 {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n <= 0) return res;
        LinkedList<Integer> track = new LinkedList<>();

        //注意这里的start初始值为1，就是为了去掉[]这个子树，直接从“1开头的子树”开始
        backtrack(n, k, track, 1);
        return res;
    }

    public void backtrack(int n, int k, LinkedList<Integer> track, int start) {
        //截至条件：track中需要存放和k长度相同的子树
        if(k==track.size()){
            res.add(new LinkedList(track));
            return;
        }
        //需要一个start来防止子集重复，即实现以“某个数开头的子集”
        for (int i = start; i <=n; i++) {
            track.add(i);
            //进入下一层决策树
            backtrack(n, k,track, i + 1);
            track.removeLast();
        }
    }
}
